Print all primes (sieve_of_eratosthenes) <= N

Print all primes (sieve_of_eratosthenes)

smaller than or equal to a specified number.

In mathematics, the sieve of Eratosthenes, one of a number

of prime number sieves, is a simple, ancient algorithm

for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite

(i.e., not prime) the multiples of each prime,

starting with the multiples of 2.

def sieve_of_Eratosthenes(N):

    limit_n = N + 1

    not_prime_nums = set()
    prime_nums = []

    for i in range(2, limit_n):
        if i in not_prime_nums:
            continue

        for f in range(i * 2, limit_n, i):
            not_prime_nums.add(f)

        prime_nums.append(i)

    return prime_nums

# test
print(sieve_of_Eratosthenes(100));

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

See also

https://www.w3resource.com/python-exercises/math/python-math-exercise-21.php